package it.storm.solution;

/**
 * 面试题 16.04. 井字游戏
 * https://leetcode-cn.com/problems/tic-tac-toe-lcci/
 */
public class Solutions_mianshi_16_04 {
    public static void main(String[] args) {
//        String[] board = {"O X"," XO","X O"};  // output: "X"
//        String[] board = {"OOX","XXO","OXO"};  // output: "Draw"
//        String[] board = {"OOX","XXO","OX "};  // output: "Pending"
        String[] board = {"OX ","OX ","O  "};  // output: 'O'

        String result = tictactoe(board);
        System.out.println(result);
    }

    private static boolean hasEmpty = false;
    public static String tictactoe(String[] board) {
        int len = board.length;
        if (len == 1) {
            return board[0];
        }
        char[][] chs = new char[len][len];
        for (int i = 0; i < len; i++) {
            chs[i] = board[i].toCharArray();
        }
        // 判断 'X' 有没有获胜
        if (checkWin(chs, 'X', len)) {
            return "X";
        }
        // 判断 'O' 有没有获胜
        if (checkWin(chs, 'O', len)) {
            return "O";
        }
        // 根据是否存在空位，判断是平局“Draw”还是游戏未结束“Pending”
        return hasEmpty ? "Pending": "Draw";
    }

    public static boolean checkWin(char[][] chs, char owner, int len) {
        // 检查每一行
        boolean res = true;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (chs[i][j] != owner) {
                    res = false;
                }
                if (chs[i][j] == ' ') {
                    // 同时记录下是否存在空位
                    hasEmpty = true;
                }
            }
            if (res) {
                // 说明 i 行上，都是 owner 字符
                return true;
            }
            res = true;
        }
        // 检查每一列
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (chs[j][i] != owner) {
                    break;
                }
                if (j == len - 1) {
                    // 说明 i 列上，都是 owner 字符
                    return true;
                }
            }
        }
        // 检查主对角线
        int i = 0, j = 0;
        while (i < len) {
            if (chs[i][j] != owner) {
                break;
            }
            i ++;
            j ++;
        }
        if (i == len && j == len) {
            // 说明主对角线上，都是 owner 字符
            return true;
        }
        // 检查副对角线
        i = 0;
        j = len - 1;
        while (i < len && j >= 0) {
            if (chs[i][j] != owner) {
                break;
            }
            i ++;
            j --;
        }
        if (i == len && j == -1) {
            // 说明副对角线上，都是 owner 字符
            return true;
        }
        return false;
    }
}
